package com.now.binarysearch;

import java.util.Arrays;

/**
 * 34. 在排序数组中查找元素的第⼀个和最后⼀个位置（中等） 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 * <p>
 * 如果数组中不存在目标值 target，返回 [-1, -1]。
 * <p>
 * 进阶：
 * <p>
 * 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？ 示例 1：
 * <p>
 * 输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4]
 * <p>
 * 示例 2：
 * <p>
 * 输入：nums = [5,7,7,8,8,10], target = 6 输出：[-1,-1]
 * <p>
 * 示例 3：
 * <p>
 * 输入：nums = [], target = 0 输出：[-1,-1]
 * <p>
 * 提示：
 * <p>
 * 0 <= nums.length <= 105 -109 <= nums[i] <= 109 nums 是一个非递减数组 -109 <= target <= 109
 */
public class SearchRange {

  public static int[] searchRange(int[] nums, int target) {

    return new int[]{left_bound(nums, target), right_bound(nums, target)};
  }

  static int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
      int middle = left + (right - left) / 2;
      if (nums[middle] < target) {
        left = middle + 1;
      } else if (nums[middle] > target) {
        right = middle - 1;
      } else {
        right = middle - 1;
      }
    }
    // 检查出界情况
    if (left >= nums.length || nums[left] != target) {
      return -1;
    }
    return left;
  }

  static int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
      int middle = left + (right - left) / 2;
      if (nums[middle] < target) {
        left = middle + 1;
      } else if (nums[middle] > target) {
        right = middle - 1;
      } else {
        left = middle + 1;
      }
    }
    // 检查出界情况
    if (right <= 0 || nums[right] != target) {
      return -1;
    }
    return right;
  }

  public static void main(String[] args) {
    int[] nums = new int[]{5,7,7,8,8,10};
    System.out.println(Arrays.toString(searchRange(nums, 8)));
  }
}
